#include <bits/stdc++.h>

using namespace std;

using ll = long long;

template <ll P>
ll fpow(ll a, ll b)
{
    assert((a != 0 || b != 0) && b >= 0);
    ll res = 1;
    for (; b; b >>= 1, a = (a * a) % P)
        if (b & 1)
            res = (res * a) % P;
    return res;
}

template <ll G, ll P>
struct NTT
{
    int _n;
    int E;
    vector<int> rev;

    /**
     * @brief 构建一个 NTT 计算器
     *
     * @param n 多项式最高项数
     */
    NTT(int n)
    {
        _n = 1;
        E = 0;
        while (_n < n)
        {
            _n <<= 1;
            E++;
        }
        rev.resize(_n);
        // 逆位置对换
        for (int i = 1; i < _n; i++)
        {
            rev[i] = (rev[i >> 1] >> 1) + ((i & 1) << (E - 1));
        }
    }

    void _rNTT(vector<ll> &A, ll k)
    {
        for (int i = 0; i < _n; i++)
            if (i < rev[i])
                swap(A[i], A[rev[i]]);

        for (int e = 1; e <= E; e++)
        {
            int m = 1 << e;
            ll gn = fpow<P>(fpow<P>(G, (P - 1) / m), k);

            for (int i = 0; i < _n; i += m)
            {
                int hf = m / 2;
                ll g = 1;
                for (int j = 0; j < hf; j++)
                {
                    ll x = A[i + j];
                    ll y = (A[i + j + hf] * g) % P;
                    A[i + j] = (x + y) % P;
                    A[i + j + hf] = (x - y) % P;
                    g = (g * gn) % P;
                }
            }
        }
    }

    /**
     * @brief NTT 过程
     *
     * @param A 系数数组
     */
    void doNTT(vector<ll> &A)
    {
        _rNTT(A, 1);
    }

    /**
     * @brief NTT 逆过程
     *
     * @param A 点值数组
     */
    void doINTT(vector<ll> &A)
    {
        ll ni = fpow<P>(_n, P - 2);
        _rNTT(A, P - 2);
        for (int i = 0; i < _n; i++)
            A[i] = (A[i] * ni) % P;
    }
};

template <ll G, ll P>
struct Poly
{
    vector<ll> vec;
    int _n;

    Poly() : vec(1), _n(1)
    {
    }

    Poly(int n) : vec(n), _n(n)
    {
    }
    Poly(ll an[], int n) : vec(n), _n(n)
    {
        for (int i = 0; i < n; i++)
            vec[i] = an[i];
    }

    void clip(int n)
    {
        vec.resize(n);
        _n = n;
    }

    Poly<G, P> operator+(const Poly<G, P> &o) const
    {
        Poly<G, P> p(max(_n, o._n));

        for (int i = 0; i < p._n; i++)
        {
            p.vec[i] = ((i < _n ? vec[i] : 0) + (i < o._n ? o.vec[i] : 0)) % P;
        }
        return p;
    }

    Poly<G, P> operator-(const Poly<G, P> &o) const
    {
        Poly<G, P> p(max(_n, o._n));

        for (int i = 0; i < p._n; i++)
        {
            p.vec[i] = ((i < _n ? vec[i] : 0) - (i < o._n ? o.vec[i] : 0)) % P;
        }

        return p;
    }

    Poly<G, P> operator*(ll v) const
    {
        Poly<G, P> p(_n);

        for (int i = 0; i < _n; i++)
            p.vec[i] = (v * vec[i]) % P;

        return p;
    }

    Poly<G, P> operator*(const Poly<G, P> &o) const
    {
        NTT<G, P> ntt(_n + o._n - 1);
        Poly<G, P> p(ntt._n);

        vector<ll> expA(p._n);
        vector<ll> expB(p._n);

        for (int i = 0; i < _n; i++)
            expA[i] = vec[i];
        for (int i = 0; i < o._n; i++)
            expB[i] = o.vec[i];

        ntt.doNTT(expA);
        ntt.doNTT(expB);

        for (int i = 0; i < p._n; i++)
            p.vec[i] = (expA[i] * expB[i]) % P;

        ntt.doINTT(p.vec);

        p.clip(_n + o._n - 1);

        return p;
    }

    Poly<G, P> inv() const
    {
        assert(vec[0] != 0);
        Poly<G, P> g(1);
        g.vec[0] = fpow<P>(vec[0], P - 2);

        for (int i = 1; i < _n;)
        {
            i <<= 1;
            Poly<G, P> vk(i);
            for (int j = 0; j < i; j++)
                vk.vec[j] = (j < _n ? vec[j] : 0);
            g = g * 2 - g * g * vk;
            g.clip(i);
        }
        g.clip(_n);
        return g;
    }

    Poly<G, P> transpose() const
    {
        Poly<G, P> p(_n);
        for (int i = 0; i < _n; i++)
            p.vec[i] = vec[i];
        reverse(p.vec.begin(), p.vec.end());
        return p;
    }

    pair<Poly<G, P>, Poly<G, P>> operator/(const Poly &o) const
    {
        Poly<G, P> ar = this->transpose();
        Poly<G, P> br = o.transpose();
        br.clip(_n - o._n + 1);
        Poly<G, P> dr = ar * br.inv();
        dr.clip(_n - o._n + 1);
        Poly<G, P> d = dr.transpose();
        Poly<G, P> r = (*this) - o * d;
        r.clip(o._n);

        return make_pair(d, r);
    }

    Poly<G, P> derivation() const
    {
        Poly<G, P> p(_n - 1);
        for (int i = 1; i < _n; i++)
            p.vec[i - 1] = (vec[i] * i) % P;
        return p;
    }

    Poly<G, P> integral(ll c) const
    {
        Poly<G, P> p(_n + 1);
        p.vec[0] = c;
        for (int i = 0; i < _n; i++)
            p.vec[i + 1] = (vec[i] * fpow<P>(i + 1, P - 2)) % P;
        return p;
    }

    Poly<G, P> ln() const
    {
        assert((vec[0] + P) % P == 1);
        Poly<G, P> p = ((*this).derivation() * (*this).inv()).integral(0);
        p.clip(_n);
        return p;
    }

    Poly<G, P> exp() const
    {
        assert((vec[0] + P) % P == 0);
        Poly<G, P> q(1);
        q.vec[0] = 1;

        for (int i = 1; i < _n;)
        {
            i <<= 1;
            Poly<G, P> vk(i);
            for (int j = 0; j < i; j++)
                vk.vec[j] = (j < _n ? vec[j] : 0);
            q.clip(i);
            Poly<G, P> v = vk - q.ln();
            v.vec[0] = (v.vec[0] + 1) % P;
            q = q * v;
            q.clip(i);
        }
        q.clip(_n);
        return q;
    }

    Poly<G, P> pow(ll k) const
    {
        Poly<G, P> q(_n);
        int p = -1;
        for (int i = 0; i < _n; i++)
        {
            if (vec[i] != 0)
            {
                p = i;
                break;
            }
        }

        if (p == -1)
            return Poly<G, P>(1);

        ll a = vec[p];
        ll ia = fpow<P>(a, P - 2);
        ll ak = fpow<P>(a, k);
        for (int i = 0; i < _n; i++)
        {
            q.vec[i] = vec[i + p] * ia % P;
        }
        q = (q.ln() * k).exp();
        Poly<G, P> v(_n);
        for (int i = 0; i < _n; i++)
        {
            if (i + k * p >= _n)
                break;
            v.vec[i + k * p] = (q.vec[i] * ak) % P;
        }
        return v;
    }
};

const ll mod = 998244353;
const ll g = 3;